package com.smh;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @author shiminghui
 * @date 2025/3/17 16:16
 * @description: TODO
 */
public class _058_分钢筋问题 {

    @Test
    public void test1() {
        Item item = new Item(1, 3, 5);
        Item item2 = new Item(2, 4, 6);
        Item item3 = new Item(3, 5, 7);
        Item[] items = new Item[]{item, item2, item3};
        System.out.println(getMax(items, 10));
    }

    /**
     * 讲一段n长的钢筋进行分段,
     * 1  2  3  4  5  // 5个分段
     * 1  3  5  7  9  // 对应的价格
     * 求分段后的最大价格
     *
     * @return
     */
    private int getMax(Item[] items, int n) {
        int[][] dp = new int[items.length][n + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (i == 0) {
                    if (j >= items[i].length) {
                        dp[i][j] = dp[i][j - items[i].length] + items[i].value;
                    }
                } else {
                    if (j >= items[i].length) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - items[i].length] + items[i].value);
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            System.out.println(Arrays.toString(dp[i]));
        }
        return dp[items.length - 1][n];
    }

    private static class Item {
        int id;
        int length;
        int value;

        public Item(int id, int length, int value) {
            this.id = id;
            this.length = length;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Item{" +
                    "id=" + id +
                    ", length=" + length +
                    ", value=" + value +
                    '}';
        }
    }


}
